package main.datastruc;

import java.util.Arrays;

public class MaxHeap<T extends Comparable<T>> {
    private T[] data;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        // 0号位不使用
        data = (T[]) new Comparable[capacity + 1];
        this.capacity = capacity;
    }

    public static void main(String[] args) {
        MaxHeap<Integer> heap = new MaxHeap<>(8);
        System.out.println(heap.size);
        for (int i = 0; i < 8; ++i) {
            heap.insert(i);
        }
        System.out.println(heap.size == heap.capacity);
        System.out.println(heap);
        System.out.println(heap.size);
        for (int i = 0; i < 8; ++i) {
            System.out.println(heap.delMax());
            System.out.println(heap);
        }
    }

    @Override
    public String toString() {
        return "MaxHeap{" + "data=" + Arrays.toString(data) + '}';
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void insert(T val) {
        if (size == capacity) {
            throw new IndexOutOfBoundsException("已满");
        }
        data[++size] = val;
        swim(size);
    }

    public T delMax() {
        if (size == 0) {
            throw new NullPointerException("为空");
        }
        T max = data[1];
        swap(1, size);
        data[size--] = null;
        sink(1);
        return max;
    }

    /**
     * 由上至下的堆有序化（上浮）
     *
     * @param k 根节点对应数组下标
     */
    private void swim(int k) {
        while (k > 1 && less(k >> 1, k)) {
            swap(k >> 1, k);
            k >>= 1;
        }
    }

    private void sink(int k) {
        while ((k << 1) <= size) {
            int j = k << 1;
            if (j + 1 < size && less(j, j + 1)) {
                ++j;
            }
            if (!less(k, j)) {
                break;
            }
            swap(k, j);
            k = j;
        }
    }

    private void swap(int i, int j) {
        T tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    private boolean less(int i, int j) {
        return data[i].compareTo(data[j]) < 0;
    }
}
